package Ep06_BinaryTree.DFS.T17_0112;

import Ep06_BinaryTree.TreeNode;

/**
 * @author Jimmy Zhan WORKSTATION
 * @date 2023/5/29 10:01
 * 说明：leetcode 0112 路径总和
 *
 * 笔记：
 * 关于方法2的回溯在哪里
 * 因为 targetSum是基本数据类型，作用域只在当前调用的方法内，当前方法return结束调用后，回到上一个方法，取到内存中栈空间的targetSum值，相当于自动回溯了
 * 但是这仅限于基本数据类型，对于引用数据类型，无论方法递归多少次，内存栈空间中的该值都是一个地址，而该地址指向的引用数据类型是没有发生改变的
 * 因此引用数据类型一定要手动回溯
 */

public class Mine {
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if (root == null) {
            return false;
        }
        // 到了叶子节点就判定是否是要求的路径
        if (root.left == null && root.right == null) {
            return targetSum == root.val;
        }
        // 不遍历空节点，因此加一层判断
        // 传参targetSum - root.val，函数结束targetSum不变，隐式回溯
        if (root.left != null) {
            if (hasPathSum(root.left, targetSum - root.val)) return true;
        }
        if (root.right != null) {
            if (hasPathSum(root.right, targetSum - root.val)) return true;
        }
        return false;
    }



    public boolean hasPathSum2(TreeNode root, int targetSum) {
        if (root == null) {
            return false;
        }
        targetSum -= root.val;
        // 到了叶子节点就判定是否是要求的路径
        if (root.left == null && root.right == null) {
            return targetSum == 0;
        }
        // 不遍历空节点，因此加一层判断
        // 传参targetSum - root.val，函数结束targetSum不变，隐式回溯
        if (root.left != null) {
            if (hasPathSum2(root.left, targetSum)) return true;
        }
        if (root.right != null) {
            if (hasPathSum2(root.right, targetSum)) return true;
        }
        return false;
    }

}
